package 算法.leetcode.offer;

import 算法.leetcode.offer.base.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author lchenglong
 * @date 2022/4/27
 */
public class Offer34 {

    List<List<Integer>> ans = new ArrayList<>();

    int target;

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        this.target = target;
        // 边界条件
        if (root == null) return new ArrayList<>();
        List<Integer> sub = new ArrayList<>();
        sub.add(root.val);
        // 只有一个节点
        if (root.val == target && root.left == null && root.right == null) {
            ans.add(Arrays.asList(root.val));
        }

        // 遍历左右子树

        dfs(root.left, root.val, sub);
        dfs(root.right, root.val, sub);
        return ans;
    }

    public void dfs(TreeNode root, int sum, List<Integer> res) {
        if (root == null) return;
        sum += root.val;
        if (sum == target && root.left == null && root.right == null) {
            List<Integer> sub = new ArrayList<>(res);
            sub.add(root.val);
            ans.add(sub);
            return;
        } else {
            List<Integer> sub = new ArrayList<>(res);
            sub.add(root.val);
            dfs(root.left, sum, sub);
            dfs(root.right, sum, sub);
        }
    }
}
